package com.wlr.study.leetcode.codethink;

/**
 * 使用此算法的前提是有序的数组并且数组内无重复元素
 * 如果有重复元素使用二分法返回的下标可能不是唯一的
 * <p>
 * 最重要的是区间的选择，有两种选择
 * 一、左右都闭合
 * 二、左闭右开
 * 对于边界的值的处理把握好度
 *
 * @author lrwang
 * @date 2022/01/06
 */
public class Dichotomy {
    public static int getIndexRightClose(int[] nums, int target) {
        // 定义target在左闭右闭的区间里，[left,right]
        int left = 0, right = nums.length - 1;
        //left=right 的时候依然是好使的所以有=
        while (left <= right) {
            // 防止溢出，等同于(left+right)/2
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                //target 在左区间 所以[left,middle-1]
                right = middle - 1;
            } else if (nums[middle] < target) {
                //target 在右区间 所以[left,middle-1]
                left = middle + 1;
            } else {
                //找到目标值直接返回
                return middle;
            }
        }
        return -1;
    }

    public static int getIndexRightOpen(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 请必须使用时间复杂度为 O(log n) 的算法。
     *
     * @param nums   数组
     * @param target 目标值
     * @return 下标
     */
    public static int getSearchInsertIndex(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                return middle;
            }
        }
        return right + 1;
    }

    /**
     * 查找一个元素在数组的区间
     *
     * @param nums   数组
     * @param target 目标值
     * @return 区间
     */
    public static int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    public static int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        System.out.println(Dichotomy.getIndexRightOpen(nums, 2));
        System.out.println(Dichotomy.getSearchInsertIndex(nums, 6));
        int[] ints = Dichotomy.searchRange(nums, 8);
        for (int a :
                ints) {
            System.out.println(a);

        }
    }
}
